The present disclosure relates to graph matching, and more particularly to an alternating and projected procedure for aligning graphs.
The notion of graph similarity and alignment appears in numerous fields, including protein-protein alignment, chemical compound comparison, optical character recognition, information extraction for finding synonyms in a single language or translation between different languages, answering similarity queries in databases, pattern recognition, etc.
Existing methods attempt to solve the graph matching or alignment problem using, for example, probabilistic techniques, genetic algorithms, decision trees, expectation-maximization, clustering techniques, and graph edit distance. The exact algorithms that solve the graph alignment problem are exponential and, thus, inapplicable to the large-scale graphs.